import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: BM89 合并区间
 * <a href="https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=295&tqId=691&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Date: 2023-07-05
 * Time: 22:29
 */

class Interval {
    int start;
    int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Solution {
    /**
     * 解题思路: (排序+贪心)
     *          时间复杂度: O(n*logn)
     *          空间复杂度: O(1) (res为返回必要空间,因此为O(1))
     * 第一步: 先依据每一个区间的 start 进行升序排序
     * 第二步: 遍历每一个区间,利用贪心思想进行合并.
     *        先记录第一个区间为[start,end], 然后往后遍历,且其后面区间为[start1,end1]
     *        1) 若 start1 <= end,则 end = max(end,end1) 然后继续向后遍历
     *        2) 若 start1 > end, 则将 [start,end] 加入res中
     * 第三步: 将遍历过程中的最后一个区间加入res中返回即可
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        // 判空处理
        if (intervals == null || intervals.size() == 0) {
            return res;
        }
        // 依据 start 进行升序排序
        intervals.sort((o1, o2) -> o1.start - o2.start);
        // 贪心思想处理
        Interval preInterval = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curInterval = intervals.get(i);
            if (preInterval.end >= curInterval.start) {
                preInterval.end = Math.max(preInterval.end,curInterval.end);
            } else {
                res.add(preInterval);
                preInterval = curInterval;
            }
        }
        res.add(preInterval);
        return res;
    }
}